#include <stdio.h>
#include <fcntl.h>
#include <io.h>
#include <vector>

#define DEBUG 0

unsigned int index = 0 ;
unsigned int size = 0 ;

unsigned int readByte( FILE *fp, std::vector< int > *undone ) {
  int c = fgetc( fp ) ;
  if( c == EOF )
    return 0 ;
  undone->push_back( c ) ;
  return 1 ;
}

void moveByte( FILE *fp, std::vector< int > *done, std::vector< int > *undone ) {

  while( done->size( ) >= 32 * 1024 ) {
    done->erase( done->begin( ) ) ;
  }

  done->push_back( undone->at( 0 ) ) ;
  undone->erase( undone->begin( ) ) ;
  readByte( fp, undone ) ;

}

void putBit( unsigned int b ) {

  static int byte = 0 ;

  byte = byte | ( b << index ) ;
  index++ ;

  if( index >= 8 ) {
    printf( "%c", byte ) ;
    byte = 0 ;
    index = 0 ;
    size++ ;
  }  

}

void flushByte( ) {

  while( index != 0 ) {
    putBit( 0 ) ;
  }

  while( size & 1 == 1 ) {
    putBit( 0 ) ;
  }

}

void outputData( int c, unsigned int width ) {
  for( unsigned int i = 0; i < width; i++ ) {
    putBit( ( c >> ( width - 1 - i ) ) & 1 ) ;
  }
}

void outputByte( int c ) {

  if( DEBUG )
    printf( "%c\n", c ) ;

  if( c <= 0x8f ) {
    c += 0x30 ;
    outputData( c, 8 ) ;
  } else {
    c += 0x190 - 0x90 ;
    outputData( c, 9 ) ; 
  }
}

void outputExt( unsigned int ext, unsigned int width ) {

  if( DEBUG )
    printf( "\ne=%d, w=%d\n", ext, width ) ;

  for( unsigned int i = 0; i < width; i++ ) {
    putBit( ext & 1 ) ;
    ext >>= 1 ;
  }
}

void outputLength( unsigned int length ) {

  if( length <= 10 ) {
    outputData( length + 254, 7 ) ;
  } else if( length == 258 ) {
    outputData( 285 - 280 + 0xc0, 8 ) ;
  } else {
    unsigned int count = 0 ;
    length -= 3 ;
    unsigned int tmp = length ;
    unsigned int pow = 1 ;
    unsigned int mask = 0 ;
    while( tmp > 1 ) {
      tmp >>= 1 ;
      pow <<= 1 ;
      count++ ;
    }
    count -= 2 ;
    for( unsigned int i = 0; i < count; i++ ) {
      mask = ( mask << 1 ) | 1 ;
    }
    unsigned num = 4 * ( count - 1 ) + ( ( length - pow ) / ( pow >> 2 ) ) + 265 ;
    if( num < 280 ) {
      outputData( num - 256, 7 ) ;
    } else {
      outputData( num - 280 + 0xc0, 8 ) ;
    }
    outputExt( length & mask, count ) ;
  }

}

void outputDistance( unsigned int distance ) {

  if( distance <= 4 ) {
    outputData( distance - 1, 5 ) ;
  } else {
    unsigned int count = 0 ;
    distance -= 1 ;
    unsigned int tmp = distance ;
    unsigned int pow = 1 ;
    unsigned int mask = 0 ;
    while( tmp > 1 ) {
      tmp >>= 1 ;
      pow <<= 1 ;
      count++ ;
    }
    count -= 1 ;
    for( unsigned int i = 0; i < count; i++ ) {
      mask = ( mask << 1 ) | 1 ;
    }
    unsigned num = 2 * ( count - 1 ) + ( ( distance - pow ) / ( pow >> 1 ) ) + 4 ;
    outputData( num, 5 ) ;
    outputExt( distance & mask, count ) ;
  }

}

void outputLengthAndDistance( unsigned int length, unsigned int distance ) {

  if( DEBUG ) 
    printf( "\nl=%d, d=%d\n", length, distance ) ;

  outputLength( length ) ;
  outputDistance( distance ) ;

}

unsigned int checkMatch( FILE *fp, std::vector< int > *done, std::vector< int > *undone ) {

  if( undone->size( ) < 3 ) 
    return 0 ;

  if( done->size( ) < 3 ) {
    outputByte( undone->at( 0 ) ) ;
    moveByte( fp, done, undone ) ;
    return 0 ;
  }

  unsigned int length = 0 ;
  unsigned int distance = 0 ;
  for( unsigned int i = 0; i < done->size( ) - 2; i++ ) {
    if( undone->at( 0 ) == done->at( i ) &&
        undone->at( 1 ) == done->at( i + 1 ) &&
        undone->at( 2 ) == done->at( i + 2 ) ) {
      unsigned int j = 0 ;
      while( j < 258 && j < undone->size( ) && i + j < done->size( ) ) {
        if( undone->at( j ) != done->at( i + j ) )
          break ;
        j++ ;
      }
      if( j > length ) {
        length = j ;
        distance = done->size( ) - i ;
      }
    }
  }

  if( length > 0 ) {
    outputLengthAndDistance( length, distance ) ;
    for( unsigned int i = 0; i < length; i++ ) {
      moveByte( fp, done, undone ) ;
    }
    return 1 ;
  }

  outputByte( undone->at( 0 ) ) ;
  moveByte( fp, done, undone ) ;

  return 0 ;

}

void flushQueue( std::vector< int > *q ) {
  while( ! q->empty( ) ) {
    outputByte( q->at( 0 ) ) ;
    q->erase( q->begin( ) ) ;
  }
}

void displayQueues( std::vector< int > *done, std::vector< int > *undone ) {

  printf( "\n" ) ;

  for( unsigned int i = 0; i < done->size( ); i++ ) {
    printf( "%02x", done->at( i ) ) ;
  }

  printf( " " ) ;

  for( unsigned int i = 0; i < undone->size( ); i++ ) {
    printf( "%02x", undone->at( i ) ) ;
  }

  printf( "\n" ) ;

}

int main( int argc, char **argv ) {

  if( argc != 2 ) {
    printf( "usage: %s <input file name>\n", argv[ 0 ] ) ;
    return -1 ;
  }

  FILE *fp ;
  if( ! ( fp = fopen( argv[ 1 ], "rb" ) ) ) {
    printf( "can't read input file %s\n", argv[ 1 ] ) ;
    return -1 ;
  }

  setmode( fileno( stdout ), O_BINARY ) ;

  std::vector< int > undone ;
  std::vector< int > done ;

  for( unsigned int i = 0; i < 258; i++ ) {
    if( ! readByte( fp, &undone ) )
      break ;
  }

  putBit( 1 ) ;
  putBit( 1 ) ;
  putBit( 0 ) ;

  while( undone.size( ) >= 3 ) {
    checkMatch( fp, &done, &undone ) ;
    if( DEBUG )
      displayQueues( &done, &undone ) ;
  }

  flushQueue( &undone ) ;
  for( unsigned int i = 0; i < 6; i++ ) {
    putBit( 0 ) ;
  }
  flushByte( ) ;

  fclose( fp ) ;

  return 0 ;

}

